package com.yiguang.algorithm.dp;

/*
 * 二维平面类问题
 * https://www.jianshu.com/p/94f34a72fdf8
 */
public class TwoDPlaneProblem {
	
	private int size;
	private int[] rowArr;
	private int[] columnArr;
	private int rowLength;
	private int colLength;
	private String targetWord;
	private char[][] source;
	
	public TwoDPlaneProblem(char[][] plane, String word) {
		targetWord = word;
		source = plane;
		size = word.length();
		rowLength = source.length;
		colLength = source[0].length;
		rowArr = new int[size];
		columnArr = new int[size];
	}

	public boolean queryWord() {
		for(int i=0; i<rowLength; i++) {
			for(int j=0; j<colLength; j++) {
				if(targetWord.charAt(0) == source[i][j]) {
					rowArr[0] = i;
					columnArr[0] = j;
					if(queryChar(i, j, 1)) {
						return true;
					}
				}
			}
		}
		return false;
	}
	
	/*
	 * 方案一
	 */
	public boolean queryChar(int rowi, int columnj, int index) {
		if(index == size) {
			return true;
		}
		// top
		if(rowi-1>=0) {
			if(targetWord.charAt(index) == source[rowi-1][columnj] && isExist(rowi-1, columnj, index)) {
				rowArr[index] = rowi-1;
				columnArr[index] = columnj;
				if(queryChar(rowi-1, columnj, index+1)) {
					return true;
				}
			}
		}
		// right
		if(columnj+1<colLength) {
			if(targetWord.charAt(index) == source[rowi][columnj+1] && isExist(rowi, columnj+1, index)) {
				rowArr[index] = rowi;
				columnArr[index] = columnj+1;
				if(queryChar(rowi, columnj+1, index+1)) {
					return true;
				}
				
			}
		}
		// bottom
		if(rowi+1<rowLength) {
			if(targetWord.charAt(index) == source[rowi+1][columnj] && isExist(rowi+1, columnj, index)) {
				rowArr[index] = rowi+1;
				columnArr[index] = columnj;
				if(queryChar(rowi+1, columnj, index+1)) {
					return true;
				}
			}
		}
		// left
		if(columnj-1>=0) {
			if(targetWord.charAt(index) == source[rowi][columnj-1] && isExist(rowi, columnj-1, index)) {
				rowArr[index] = rowi;
				columnArr[index] = columnj-1;
				if(queryChar(rowi, columnj-1, index+1)) {
					return true;
				}
			}
		}
		return false;
	}
	
	/*
	 * 方案二：不可行，待完善
	 */
	public boolean queryChar2(int rowi, int columnj, int index) {
		if(index == size) {
			return true;
		}
		for(int i=0; i<4; i++) {
			int currentRow = rowi;
			int currentCol = columnj;
			if(i==0) {
				currentRow = currentRow-1;
			}else if(i==1){
				currentCol = currentCol+1;
			}else if(i==2) {
				currentRow = currentRow+1;
			}else {
				currentCol = currentCol-1;
			}
			if(currentRow<0||currentRow>=rowLength||currentCol<0||currentCol>=colLength) {
				return false;
			}
			if(targetWord.charAt(index) == source[currentRow][currentCol] && isExist(currentRow, currentCol, index)) {
				rowArr[index] = currentRow;
				columnArr[index] = currentCol;
				if(queryChar2(currentRow, currentCol, index+1)) {
					return true;
				}
			}
		}
		return false;
	}
	
	//用于判断元素是否可使用
	public boolean isExist(int row, int column, int index) {
		for(int i=0; i<index; i++) {
			if(rowArr[i]==row&&columnArr[i]==column) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		/*
		 * ABCE
		 * SFCS
		 * ADEE
		 * VMNR
		 */
		char[][] plane = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'},{'V','M','N','R'}};
		TwoDPlaneProblem twoDPlaneProblem = new TwoDPlaneProblem(plane, "DEER");
		System.out.println(twoDPlaneProblem.queryWord());
	}
}
